// 最长递增子序列算法：求最大递增的个数
/**
 * 贪心 + 二分查找
 * 情况一：在查找的过程中，如果当前的值比已经查找出来的列表的最后一个还大，就直接插入
 * 情况二：在查找的过程中，如果当前的值比已经查找出来的列表的最后一个还小，
 *        就采用二分查找，找到已经排好的列表，找到比当前的值大的那一项，将其替换掉
 *        但是最终的结果列表不正确，需要调整
 * 例如：[2, 3, 1, 5, 6, 8, 7, 9, 4]
 2
 2 3
 1 3
 1 3 5
 1 3 5 6
 1 3 5 6 8
 1 3 5 6 7
 1 3 5 6 7 9
 1 3 4 6 7 9 // 结果列表不正确但长度没问题

 1 3 4 6 7 9 对应原列表的索引 2 1 8 4 6 7

 需要的正确的最终的结果是 2 3 5 6 7 9 对应的索引 0 1 3 4 6 7
 */
function getSequenceDemo(arr) { // 返回的是索引的数组
  const len = arr.length;
  const result = [0]; // result 存储索引

  const p = arr.slice(0); // p 存储索引

  let start, end, middle;
  for (let i = 0; i < len; i++) {
    const arrIndex = arr[i];
    if (arrIndex !== 0) {
      let resultLastIndex = result[result.length - 1];
      // 当前值比上一个大
      if (arr[resultLastIndex] < arrIndex) {
        p[i] = resultLastIndex;
        result.push(i);
        continue;
      }
      
      start = 0;
      end = result.length - 1;
      
      // 二分查找
      while(start < end) {
        middle = ((start + end) / 2) | 0; // | 0 主要是取整
        // 找到比当前值大的那一个
        if (arr[result[middle]] < arrIndex) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }
      // 如果相同或者比当前值还大就不需要交换位置
      if (arrIndex < arr[result[start]]) {
        if (start > 0) {
          p[i] = result[start - 1]; // 替换前一个数据
        }
        result[start] = i;
      }
    }
  }

  let l = result.length;
  let last = result[l - 1];
  // 根据前驱节点向前查找
  while(l-- > 0) {
    result[l] = last;
    last = p[last];
  }

  return result;
}


// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
export function getSequence(arr: number[] = []): number[] {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      while (u < v) {
        c = (u + v) >> 1
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

// const arr = [2, 3, 1, 5, 6, 8, 7, 9, 4];
// console.log(getSequenceDemo(arr));
// console.log(getSequence(arr));